Para la primera función, ¿no debería estar "prev = head" fuera de else porque queremos establecer el anterior cada vez antes de cambiar el valor de head?
Para la segunda función, ¿no debería estar "p2 = p2.next" fuera de else porque queremos ir a continuación cada vez?
Gracias chicos.
//This would take O(n) but would require extra space O(n) public static Node removeDuplicates(Node head){ Node prev = null; Set<Integer> hs = new HashSet<Integer>(); while(head!= null){ if(hs.contains(head.data)){ prev.next = head.next; } else{ hs.add(head.data); //why is prev = head here instead of out of the else statement? prev = head; } head = head.next; } return head; } //This would take O(n^2) but no extra space is required. public static Node removeDuplicatesTradeOff(Node head){ //pointer 1 and pointer 2. Node p1 = head; while(p1.next != null){ Node p2 = p1; while(p2.next != null){ if(p1.data == p2.next.data){ p2.next = p2.next.next; } else{ //why is p2 = p2.next here instead of out of the else statement? p2 = p2.next; } } p1 = p1.next; } return head; }Usando la solución 1 como referencia porque la respuesta se aplica a ambas soluciones. Cuando encuentra un duplicado en el nodo actual ( head ), establece el next nodo del nodo anterior ( prev ) en el next nodo del nodo actual (que elimina el duplicado). En la siguiente iteración, irá al siguiente nodo de la lista que ya está siendo señalado por el nodo anterior. Por lo tanto, no hay necesidad de sobrescribir prev . Otra forma de pensarlo es que la head que estaría configurando como prev es el nodo que acaba de eliminar. No querrías hacer eso.
Antes de la eliminación: nodo1 (anterior) -> nodo2 (cabeza) -> nodo3
Después de la eliminación: nodo1 (anterior) -> nodo3 (cabeza)
Como puede ver, prev permanece igual. No es necesario actualizarlo.
¿No debería "p2 = p2.next" estar fuera de otra cosa porque queremos ir a continuación cada vez
Creo que sería más exacto decir que queremos tener un próximo diferente disponible cada vez , en lugar de decir que queremos "ir al siguiente" cada vez.
No siempre queremos "ir a continuación". Cuando prev.next ha cambiado debido a otra operación (en este caso, eliminación de un duplicado), queremos permanecer donde estamos, porque prev.next ya ha cambiado y ahora apunta a un nodo más adelante (porque acaba de aparecer un nodo duplicado). sido eliminado).
En otras palabras, no queremos tener una prev diferente cada vez, solo queremos tener una prev.next diferente cada vez. Entonces, siempre que prev.next avance cada vez, no nos importa si prev permanece igual a veces.
Es por eso que en ambos métodos prev (o p2 ) solo avanza en la rama else , mientras que prev.next (o p2.next ) se actualiza (avanza) solo en la rama if .
Piense en estas dos como operaciones diferentes, la rama else es "ir a continuación" y la rama if es "caer a continuación". Cuando soltaste un nodo delante de ti, no te moviste (¡verdadero!), pero como soltaste un nodo delante de ti, ahora hay un nuevo nodo delante de ti, así que no tienes que moverte. Entonces puede continuar con las comprobaciones if/else y tarde o temprano llegará al final o dejará caer el último nodo delante de usted.
Un ejemplo de entrada para ilustrar este punto es
head(1) -> 1 -> 1 -> 1 -> nullCon tal entrada, el algoritmo solo haría
y estaría hecho.
Ningún "ir a continuación" sucedió en absoluto.
Resultado
head(1) -> nullremoveDuplicates :
Si eliminamos un duplicado, el nodo eliminado actual no debe asignarse a prev . De hecho, prev es el nodo anterior en la lista restante de únicos.
Como es del todo evidente, cuando hay más de 2 valores repetidos.
... -> prev: [42] -> [42] -> [42] -> [51] -> ...debe convertirse
... -> prev: [42] -> [51] -> ...removeDuplicatesTradeOff:
El mismo caso. p2 (el nodo anterior) solo puede avanzar cuando no se encontró ningún duplicado.
Luego hay un pequeño error:
removeDuplicates debería devolver el nuevo head normalmente, en caso de que se elimine el nodo principal:
head = remove...(head); // Must assign, should the head node itself be removed. Ahora devuelve null . Sin embargo, para los duplicados, el nodo principal nunca se elimina. Entonces, conviértalo en una función void o devuelva la head anterior.
public static Node removeDuplicates(Node head){ Node prev = null; Set<Integer> hs = new HashSet<>(); Node current = head; // Loop-invariant: hs.isEmpty() || prev != null while (current != null) { if (hs.contains(current.data)) { prev.next = current.next; } else { hs.add(current.data); prev = current; } current = current.next; } return head; } También tenga en cuenta que es de mal estilo usar el nombre head para un puntero en ejecución.